/*采用邻接矩阵存储图*/
#include<iostream>
#include<cstring>
#include<queue> 
#include<map> 
using namespace std;

const int INF = 0x3f3f3f3f;
const int MVNum = 100;			//最大顶点数 
int visited[MVNum];				//访问数组 
map<char, int> mp;

typedef struct {					//邻接矩阵存储无向图 
	char vexs[MVNum];			//顶点数据
	int arcs[MVNum][MVNum];		//边的权值
	int vexnum, arcnum;			//图的点数和边数 
}Graph;

void CreateGraph(Graph& G) {
	int w;
	char v1, v2;
	cout << "输入图的顶点数和边数：" << endl;
	cin >> G.vexnum >> G.arcnum;
	cout << "依次输入" << G.vexnum << "个顶点：" << endl;
	for (int i = 0; i < G.vexnum; ++i) {
		cin >> G.vexs[i];
		mp[G.vexs[i]] = i;		//顶点在图中的位置即为顶点的输入次序
	}
	memset(G.arcs, INF, sizeof(G.arcs));	//初始化邻接矩阵 
	cout << "依次输入" << G.arcnum << "条边的两个顶点和权值" << endl;
	for (int i = 0; i < G.arcnum; ++i) {
		cin >> v1 >> v2 >> w;
		G.arcs[mp[v1]][mp[v2]] = w;
		G.arcs[mp[v2]][mp[v1]] = w;
	}
}

void DFS(Graph G, int v) {
	cout << G.vexs[v];
	visited[v] = 1;
	for (int w = 0; w < G.vexnum; ++w) {
		if ((!visited[w]) && (G.arcs[v][w] != INF)) {
			DFS(G, w);
		}
	}
}

void BFS(Graph G, int v) {
	cout << G.vexs[v];
	visited[v] = 1;
	queue<int> Q; 	//STL
	Q.push(v);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int w = 0; w < G.vexnum; ++w) {
			if ((!visited[w]) && (G.arcs[u][w] != INF)) {
				cout << G.vexs[w];
				visited[w] = 1;
				Q.push(w);
			}
		}
	}

}

int main() {
	Graph G;
	CreateGraph(G);
	cout << "DFS:" << endl;
	DFS(G, 0);		//从第0个顶点开始DFS
	memset(visited, 0, sizeof(visited));	//重新初始化visited数组
	cout << endl << "BFS:"<<endl;
	BFS(G, 0);		//从第0个顶点开始BFS 
	return 0;
}
